﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using Core.Primitives;

using LabelHashSetList = System.Collections.Generic.List<System.Collections.Generic.HashSet<int>>;
using LabelHashSet = System.Collections.Generic.HashSet<int>;

namespace Core
{
    public static class ConnectedRegionContourFinder
    {
        public enum ConnectivityType
        {
            EightConnectivity,
            FourConnectivity
        }
        private static void UpdateRegionEquivalence(LabelHashSetList hsl, List<int> labels)
        {
            Dictionary<int, LabelHashSet> appropriateHashSets = new Dictionary<int, LabelHashSet>();

            foreach (var hs in hsl)
            {
                foreach (var label in labels)
                {
                    if (hs.Contains(label))
                    {
                        appropriateHashSets[label] = hs;
                        break;
                    }
                }
            }

            if (appropriateHashSets.Count == 0)
            {
                hsl.Add(new LabelHashSet(labels));
            }
            else //if (appropriateHashSets.Count >= 1)
            {
                //appropriateHashSets.Single(
                LabelHashSetList hashSetsToMerge = appropriateHashSets.Select(pair => pair.Value).ToList();

                // add all our equivalent labels into first hashSet (doesn't matter)
                labels.ForEach(label => hashSetsToMerge[0].Add(label));

                for (int i = 1; i < hashSetsToMerge.Count; i++)
                {
                    LabelHashSet mergingHashSet = hashSetsToMerge[i];

                    foreach (var label in mergingHashSet)
                    {
                        hashSetsToMerge[0].Add(label);
                    }

                    hsl.Remove(mergingHashSet);
                }
            }
        }
        private static int FindMinEquivalence(LabelHashSetList hsl, int label)
        {
            foreach (var hs in hsl)
            {
                if (hs.Contains(label))
                    return hs.Min();
            }

            return label;
        }
        /// <summary>
        /// Returns array with uniquely regions labels (used 4-connectivity).       
        /// Based on <see cref="http://en.wikipedia.org/wiki/Connected-component_labeling"/>
        /// </summary>
        public static Matrix<int> LabelConnectedRegions(DataField field, ConnectivityType connectivityType)
        {
            int h = field.Size.Height;
            int w = field.Size.Width;

            Matrix<int> labels = new Matrix<int>(h, w);

            // first pass
            int uniqueRegionLabel = 1;

            LabelHashSetList regionEquivalence = new LabelHashSetList();

            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    DataPoint current = field[i, j];
                    DataPoint[] neighbors;

                    switch (connectivityType)
                    {
                        case ConnectivityType.EightConnectivity:
                            neighbors = new DataPoint[4] // 8-connectivity
                            {
                                field[i, j - 1],
                                field[i - 1, j - 1],
                                field[i - 1, j],
                                field[i - 1, j + 1]
                            };
                            break;
                        case ConnectivityType.FourConnectivity:
                            neighbors = new DataPoint[2] // 4-connectivity
                            {
                                field[i, j - 1],
                                field[i - 1, j]
                            };
                            break;
                        default:
                            throw new ArgumentException("Unknown connectivity");
                    }

                    var sameTypeNeighbors = neighbors
                        .Where(dp => dp != null && dp.Type == current.Type)
                        .Select(dp => labels[dp.DiscretePosition])
                        .Distinct()
                        .ToList();

                    if (sameTypeNeighbors.Count >= 2)
                        UpdateRegionEquivalence(regionEquivalence, sameTypeNeighbors);

                    if (sameTypeNeighbors.Count >= 1)
                        labels[i, j] = sameTypeNeighbors.Min();
                    else
                        labels[i, j] = uniqueRegionLabel++;
                }
            }

            // second pass
            Dictionary<int, int> equivalenceCache = new Dictionary<int, int>();

            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    if (!equivalenceCache.ContainsKey(labels[i, j]))
                    {
                        equivalenceCache[labels[i, j]] = FindMinEquivalence(regionEquivalence, labels[i, j]);
                    }

                    labels[i, j] = equivalenceCache[labels[i, j]];
                }
            }

            return labels;
        }
        public static IEnumerable<SinglePolyline> GetContours(DataField dataField, ConnectivityType connectivityType = ConnectivityType.FourConnectivity)
        {
            Matrix<int> labels = LabelConnectedRegions(dataField, connectivityType);

            return GetContours(dataField, labels);
        }
        public static IEnumerable<SinglePolyline> GetContours(DataField dataField, Matrix<int> labels)
        {
            List<RegionInfo> regionInfos = GetRegionInfos(dataField, labels);
            List<SinglePolyline> contours = new List<SinglePolyline>();

            foreach (var regionInfo in regionInfos)
            {
                contours.Add(GetContour(dataField, labels, regionInfo));
            }

            return contours;
        }

        private static SinglePolyline GetContour(DataField field, Matrix<int> labels, RegionInfo regionInfo)
        {
            // knotPosition matchs left bottom corner of data point in data field with coordinates (i, j)
            // so knotPosition.Row can be in range [0; dataField.Height]
            // and knotPosition.Column can be in range [0; dataField.Width]
            // i.e. max values by 1 more than data point max coordinates 
            // (becouse n data points in row creates n + 1 knots)
            // to get real knots (i, j) coordinates we need to substract from real (i, j) data point coordinates 
            // this value: (stepX / 2, stepY / 2)
            
            DataPoint initPoint = regionInfo.InitialPoint;
            List<IntPosition> contourPoints = new List<IntPosition>();
            HashSet<IntSegment> previousSegments = new HashSet<IntSegment>();
            IntPosition? previousPosition = null;
            IntPosition knotPosition = initPoint.DiscretePosition;

            contourPoints.Add(knotPosition);

            do
            {
                IntPosition? next = GetNextKnotPosition(field, labels, regionInfo, knotPosition, initPoint.DiscretePosition, previousPosition, previousSegments);

                if (next == null) // contour is generated
                    break;

                previousPosition = knotPosition;
                knotPosition = next.Value;

                previousSegments.Add(new IntSegment(previousPosition.Value, knotPosition));

                contourPoints.Add(knotPosition);

            } while (true);

            //contourPoints.Add(contourPoints[0]); // clojure

            return new SinglePolyline(
                contourPoints.Select(cp => KnotPositionToRealCoordinates(field, cp)).ToArray(), 
                regionInfo.InitialPoint.Type);
        }
        private static SinglePoint KnotPositionToRealCoordinates(DataField field, IntPosition knotPos)
        {
            float x = field.StartX + field.StepX * knotPos.Column;
            float y = field.StartY + field.StepY * knotPos.Row;

            return new SinglePoint(x, y);
        }
        private static IntPosition? GetNextKnotPosition(DataField field, Matrix<int> labels, RegionInfo regionInfo, IntPosition currentPosition, IntPosition startPosition, IntPosition? previousPosition, HashSet<IntSegment> previousSegments)
        {
            // we should to go so, that right (or left) "hand" is always concerned the target area
            //
            // NOTE: point in the route may be repeated, but we never have to go along the same line
            // (i.e. points never repeated one after another)
            // 
            // at the same time we should to REJECT knot in this cases:
            // - formed path doesn't concerned the target area
            // - formed path divides the target area
            //
            // check order:
            // right -> forward -> left
           
            IntPosition[] possibilities;

            if (currentPosition.Equals(startPosition)) // equivalent: previousPosition == null
            {
                possibilities = new IntPosition[4]
                {
                    currentPosition + new IntPosition(+1,0),
                    currentPosition + new IntPosition(-1,0),
                    currentPosition + new IntPosition(0,+1),
                    currentPosition + new IntPosition(0,-1)
                };
            }
            else
            {
                IntPosition leftKnot;
                IntPosition forwardKnot;
                IntPosition rightKnot;

                GetNeighborhoodKnots(previousPosition.Value, currentPosition, out leftKnot, out forwardKnot, out rightKnot);

                possibilities = new IntPosition[3]
                {
                    rightKnot,
                    forwardKnot,
                    leftKnot
                    //leftKnot,
                    //forwardKnot,
                    //rightKnot
                };
            }

            foreach (var possibility in possibilities)
            {
                if (!startPosition.Equals(possibility) &&
                    !previousSegments.Contains(new IntSegment(currentPosition, possibility))
                    && IsValidPathBetweenRegions(field, labels, currentPosition, possibility, regionInfo.Label))
                {
                    return possibility;
                }
            }

            return null;
        }
        private static void GetNeighborhoodDataPoints(
            DataField field,
            IntPosition previous, IntPosition current,
            out DataPoint left, out DataPoint right)
        {
            IntPosition leftKnotPos;
            IntPosition forwardKnotPos;
            IntPosition rightKnotPos;
            
            GetNeighborhoodKnots(previous, current, out leftKnotPos, out forwardKnotPos, out rightKnotPos);

            left = field[Min3(previous.Row, current.Row, leftKnotPos.Row), Min3(previous.Column, current.Column, leftKnotPos.Column)];
            right = field[Min3(previous.Row, current.Row, rightKnotPos.Row), Min3(previous.Column, current.Column, rightKnotPos.Column)];
        }
        private static int Min3(int v1, int v2, int v3)
        {
            return (int)Math.Min(v1, (int)Math.Min(v2, v3));
        }
        private static void GetNeighborhoodKnots(
            IntPosition previous,
            IntPosition current,
            out IntPosition left,
            out IntPosition forward,
            out IntPosition right)
        {
            IntPosition previousShift = (current - previous);

            forward = current + previousShift;

            var leftShift = new IntPosition(-previousShift.Column, previousShift.Row);
            left = current + leftShift;

            var rightShift = new IntPosition(previousShift.Column, -previousShift.Row);
            right = current + rightShift;
        }
        private static bool IsValidPathBetweenRegions(DataField field, Matrix<int> labels, IntPosition from, IntPosition to, int targetLabel)
        {
            DataPoint leftDataPoint;
            DataPoint rightDataPoint;
            
            GetNeighborhoodDataPoints(field, from, to, out leftDataPoint, out rightDataPoint);

            if (leftDataPoint == null && rightDataPoint == null)
            {
                return false;
            }
            else if (leftDataPoint != null && rightDataPoint != null)
            {
                if (labels[rightDataPoint.DiscretePosition] == targetLabel
                    && (labels[leftDataPoint.DiscretePosition] != labels[rightDataPoint.DiscretePosition])) // not target region dividing
                {
                    return true;
                }

                return false;
            }
            else
            {
                return rightDataPoint != null && labels[rightDataPoint.DiscretePosition] == targetLabel;
            }
        }
        private static List<RegionInfo> GetRegionInfos(DataField field, Matrix<int> labels)
        {
            List<RegionInfo> infos = new List<RegionInfo>();
            HashSet<int> findedLabels = new HashSet<int>();

            for (int i = 0; i < field.Size.Height; i++)
            {
                for (int j = 0; j < field.Size.Width; j++)
                {
                    int label = labels[i, j];

                    if (!findedLabels.Contains(label))
                    {
                        findedLabels.Add(label);

                        infos.Add(new RegionInfo(label, field[i, j]));
                    }
                }
            }

            return infos;
        }

        private class RegionInfo
        {
            public int Label;
            public DataPoint InitialPoint;

            public RegionInfo(int label, DataPoint someStartPoint)
            {
                Label = label;
                InitialPoint = someStartPoint;
            }
        }
    }
}
